#include "linearList.h"
#include <bits/stdc++.h>
using namespace std;

// SequenceList
sequenceList::sequenceList(const int &capacity, const int &initSize, float array[])
{
    myList = new float[capacity];
    curNumberOfItem = initSize;
    maxCapcity = capacity;
    if (myList == NULL)
    {
        maxCapcity = 0;
        curNumberOfItem = 0;
    }

    for (int i = 0; i < initSize; i++)
    {
        myList[i] = array[i];
    }
}

sequenceList::~sequenceList()
{
    delete[] myList;
}

bool sequenceList::addItem(const float &item)
{
    if (curNumberOfItem == maxCapcity)
    {
        return false;
    }
    myList[curNumberOfItem] = item;
    curNumberOfItem++;
    return true;
}

bool sequenceList::insertItem(const int &index, const float &item)
{
    if (index < 0 || index > curNumberOfItem || curNumberOfItem == maxCapcity)
    {
        return false;
    }
    else
    {
        curNumberOfItem++;
        for (int i = curNumberOfItem; i > index; i--)
        {
            myList[i] = myList[i - 1];
        }
        myList[index] = item;
        return true;
    }
}

int sequenceList::deleteItem(const float &item)
{
    for (int i = 0; i < curNumberOfItem; i++)
    {
        if (myList[i] == item)
        {
            for (int j = i; j < curNumberOfItem - 1; j++)
            {
                myList[j] = myList[j + 1];
            }
            curNumberOfItem--;
            return i;
        }
    }
    return -1;
}

bool sequenceList::locate(const int &index, float &val)
{
    if (index > curNumberOfItem - 1 || index < 0)
    {
        return 0;
    }
    val = myList[index];
    return true;
}

int sequenceList::locate(const float &item)
{
    for (int i = 0; i < curNumberOfItem; i++)
    {
        if (myList[i] == item)
        {
            return i;
        }
    }
    return -1;
}

void sequenceList::reverse()
{
    float temp = 0;
    for (int i = 0; i < curNumberOfItem / 2; i++)
    {
        temp = myList[i];
        myList[i] = myList[curNumberOfItem - 1 - i];
        myList[curNumberOfItem - 1 - i] = temp;
    }
}

// 顺序表打印
void sequenceList::print()
{
    cout << curNumberOfItem << ":";

    for (int i = 0; i < curNumberOfItem - 1; i++)
    {
        cout << myList[i] << ",";
    }

    cout << myList[curNumberOfItem - 1] << endl;
}

// linkList

linkList::linkList(const int &size, float array[])
{
    firstNode = new listNode;
    curNode = firstNode;

    listSize = size;

    for (int i = 0; i < size; i++)
    {
        listNode *newNode = new listNode;
        newNode->data = array[i];
        curNode->next = newNode;
        curNode = newNode;
    }
    curNode->next = NULL;
    lastNode = curNode;
}

linkList::~linkList()
{
    listNode *temp;
    curNode = firstNode;
    while (curNode != NULL)
    {
        temp = curNode;
        curNode = curNode->next;
        delete temp;
    }
}

bool linkList::headInsertItem(const float &val)
{
    if (firstNode == NULL)
    {
        return false;
    }
    listNode *newNode = new listNode;
    newNode->data = val;
    newNode->next = firstNode->next;
    firstNode->next = newNode;
    listSize++;
    return true;
}

bool linkList::tailInsertItem(const float &val)
{
    if (firstNode == NULL)
    {
        return false;
    }
    listNode *newnode = new listNode;
    newnode->data = val;
    newnode->next = NULL;
    lastNode->next = newnode;
    lastNode = newnode;
    listSize++;
    return true;
}

int linkList::insertItem(const int &index, const float &val)
{
    if (index < 0 || index > listSize)
    {
        return -1;
    }
    listNode *newnode = new listNode;
    newnode->data = val;
    if (index == 0)
    {
        newnode->next = firstNode;
        newnode = firstNode;
    }
    else
    {
        curNode = firstNode;
        for (int i = 0; i < index; i++)
        {
            curNode = curNode->next;
        }
        newnode->next = curNode->next;
        curNode->next = newnode;
    }
    listSize++;
    return index;
}

int linkList::deleteItem(const float &val)
{
    curNode = firstNode->next;
    listNode *temp;
    listNode *prev = firstNode;
    for (int i = 0; i < listSize - 2; i++)
    {
        if (curNode->data == val)
        {
            temp = curNode;
            prev->next = curNode->next;
            delete temp;
            listSize--;
            return i + 1;
        }
        else
        {
            curNode = curNode->next;
            prev = prev->next;
        }
    }
    if (curNode->data == val)
    {
        temp = curNode;
        prev->next = NULL;
        delete temp;
        listSize--;
        lastNode = prev;
        return listSize - 1;
    }
    return -1;
}

bool linkList::locate(const int &index, float &val)
{
    if (index < 0 || index > listSize - 1)
    {
        return false;
    }
    curNode = firstNode;
    for (int i = 0; i < index; i++)
    {
        curNode = curNode->next;
    }
    if (curNode != NULL)
    {
        val = curNode->data;
        return true;
    }
    return false;
}

int linkList::locate(const float &val)
{
    curNode = firstNode->next;
    for (int i = 0; i < listSize; i++)
    {
        if (curNode->data == val)
        {
            return i;
        }
        curNode = curNode->next;
    }
    return -1;
}

void linkList::ascendingOrder()
{
    listNode *p = firstNode->next;
    listNode *q = firstNode->next;
    listNode *h = firstNode;
    listNode *temp;
    curNode = p->next;

    if (p == NULL || p->next == NULL)
    {
        return;
    }
    for (int i = 0; i < listSize - 1; i++)
    {
        if (p->data <= curNode->data)
        {
            p = p->next;
            curNode = curNode->next;
        }
        else
        {
            p->next = curNode->next;
            temp = curNode;
            curNode = curNode->next;
            for (int j = 0; j < i + 1; j++)
            {
                if (q->data > temp->data)
                {
                    h->next = temp;
                    temp->next = q;
                    q = firstNode->next;
                    h = firstNode;
                    break;
                }
                else
                {
                    q = q->next;
                    h = h->next;
                }
            }
        }
    }
    lastNode = p;
}

void linkList::reverse()
{
    listNode *p;
    listNode *q;
    lastNode = firstNode->next;
    p = firstNode->next;
    firstNode->next = NULL;
    while (p != NULL)
    {
        q = p;
        p = p->next;
        q->next = firstNode->next;
        firstNode->next = q;
    }
}

// 链表打印
void linkList::print()
{
    curNode = firstNode;

    cout << listSize << ":";

    while (curNode != lastNode)
    {
        if (curNode->next == lastNode)
            cout << curNode->next->data << endl;
        else
        {
            cout << curNode->next->data << ",";
        }

        curNode = curNode->next;
    }
}

void linkList::combine(linkList &B)
{
    lastNode->next = B.GetFirst()->next;
    lastNode = B.GetLast();
    listSize = listSize + B.GetSize();
}

void merge(linkList &A, linkList &B)
{
    A.combine(B);
    A.ascendingOrder();
    A.reverse();
}